// 最小生成树 Prim
// 教学视频 https://www.bilibili.com/video/BV1Eb41177d1/?spm_id_from=333.880.my_history.page.click&vd_source=4fd973d19cb5506a7c9f2d59e8ab5165
// 最小生成树有两种算法: Kruskal（克鲁斯卡尔）和 Prim（普里姆）
// Prim算法，最终能将所有节点连起来，并且花费的权值最小
// Prim算法的实现逻辑：
// 从任意一个节点开始，依次获取该节点和其连接节点的权值，取权值最小的那个加入最小生成树
// Prim算法和Kijstra算法很相似，但Kijstra是用来算最短路径，不是用来算最小生成树的。两者都是从一个节点和其连接的节点开始计算，获取权值，获取最小的加入最小生成树，区别在于，Kijstra的最小权值依据取的是从起点到当前节点的距离，而Prim的最小权值依据是当前节点的路径中最小的权值即可

const { log, isNumber } = require('../commonTool/zddtool.js');

class NodeMatrix {
    constructor() {
        this.list = [];
    }

    add(node1, node2, value) {
        this.list.push(new NodeLink(node1, node2, value));
    }

    out() {
        return this.list;
    }
}

class NodeLink {
    constructor(node1, node2, value) {
        this.node1 = node1;
        this.node2 = node2;
        this.value = value;
    }

    hasNode(node) {
        if (!isNumber(node)) {
            return false;
        }

        return this.node1 === node || this.node2 === node;
    }

    linkNode(node) {
        if (!isNumber(node)) return null;

        if (this.node1 === node) {
            return this.node2;
        } else if (this.node2 === node) {
            return this.node1;
        }

        return null;
    }
}

class PrimNode {
    constructor(ID) {
        this.ID = ID;
        this.selected = false;
        this.minDist = Number.MAX_VALUE;
        this.parentID = -1;
    }
}

class Prim {
    constructor(nodeList) {
        this.primNodeList = [];
        this.sortNodeList(nodeList);
        this.initPrimNodeList(); // 初始化prim列表
        this.init();

        log(`Prim Init Complete`);
        log(this.out());
    }

    out() {
        log(`[totalValue]`);
        log(this.totalValue());

        return new Array(this.primNodeList.length)
            .fill(-1)
            .map((_, idx) => this.primNodeList[idx].minDist);
    }

    totalValue() {
        if (this.primNodeList.findIndex((ele) => !ele.selected) >= 0) return -1;

        return this.primNodeList.reduce((acc, cur) => acc + cur.minDist, 0);
    }

    sortNodeList(nodeList) {
        this.nodeList = nodeList;
        this.nodeList.sort((a, b) => a.value - b.value);
    }

    initPrimNodeList() {
        let arr = {};
        for (let ele of this.nodeList) {
            const { node1, node2 } = ele;
            [node1, node2].forEach((node) => {
                if (!arr[node]) {
                    arr[node] = 1;
                } else {
                    arr[node] += 1;
                }
            });
        }

        log(`[initPrimNodeList]`);
        log(arr);

        Object.keys(arr).forEach((key) => {
            this.primNodeList.push(new PrimNode(parseInt(key)));
        });
    }

    init() {
        // 从prim表中选一个元素，将其置为初始节点
        let pNode = this.primNodeList.find(
            (ele) => ele.ID === this.nodeList[0].node1
        );
        pNode.minDist = 0;
        pNode.parentID = pNode.ID;

        for (let i = 0; i < this.nodeList.length; i++) {
            // 从prim中，挑选一个没有没选中的，但权值最低的节点
            let currentNode = this.primNodeList
                .filter(
                    (ele) => !ele.selected && ele.minDist < Number.MAX_VALUE
                )
                .sort((a, b) => a.minDist - b.minDist)[0];

            if (currentNode == null) {
                log('error');
                log(this.out());
                break;
            }

            currentNode.selected = true;

            // 更新当前节点的相邻节点的权值
            // 在矩阵中搜索当前节点的相邻节点
            let linkNodes = this.nodeList.filter((ele) =>
                ele.hasNode(currentNode.ID)
            );

            // 更新相邻节点的权值
            linkNodes.forEach((ele) => {
                let pNode = this.primNodeList.find(
                    (pn) => pn.ID === ele.linkNode(currentNode.ID)
                );

                if (!pNode.selected && pNode.minDist > ele.value) {
                    pNode.minDist = ele.value;
                    pNode.parentID = currentNode.ID;
                }
            });
        }
    }
}

let matrix = new NodeMatrix();
matrix.add(0, 1, 4);
matrix.add(1, 2, 8);
matrix.add(2, 3, 7);
matrix.add(3, 4, 9);
matrix.add(4, 5, 10);
matrix.add(5, 6, 2);
matrix.add(6, 7, 1);
matrix.add(1, 7, 11);
matrix.add(7, 8, 7);
matrix.add(2, 8, 2);
matrix.add(6, 8, 6);
matrix.add(2, 5, 4);
matrix.add(3, 5, 14);

let primIns = new Prim(matrix.out());
